#include "SortingProvider.h"
using namespace std;

void arrcpy(int arrIn[], int arrOut[],int length, int index, int num)
{
    for(int i = index; ( i<index+num )&&( i<length ); i++)
        arrOut[i-index] = arrIn[i];
}

void Sort(int arr1[], int length1, int arr2[], int length2, int arrSum[])
{
    int i=0, j=0, k=0;
    while (i<length1 || j<length2)
    {

        arrSum[k] = (i != length1) && ((j == length2) || (arr1[i]<arr2[j]) )? arr1[i++] : arr2[j++];
        k++;

        /* explain.....
        if(i == length1)
        {
            arrSum = arr1[i];
            i++;
        }
        else if (j == length2)
        {
            arrSum = arr2[j];
            j++;
        }
        else if(arr1[i] < arr2[j])
        {
            arrSum = arr1[i];
            i++;
        }
        else
        {
            arrSum = arr2[j];
            j++;
        }
        k++;
        */
    }
}

void divide(int arr[], int length, int arr1[], int *length1, int arr2[], int *length2)
{
    *length1 = length/2;
    *length2 = length - *length1;

    arrcpy(arr, arr1, length, 0, *length1);
    arrcpy(arr, arr2, length, *length1, *length2);
}

void SortingProvider::MergeSort(int arr[], int n)
{
    if(n>1)
    {
        int arr1[10000], arr2[10000];
        int length1, length2;
        divide(arr, n, arr1, &length1, arr2, &length2);
        MergeSort(arr1, length1);
        MergeSort(arr2, length2);
        Sort(arr1, length1, arr2, length2, arr);
    }
}
